package demo10;

import java.util.*;

public class test {
    public static List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            if (map.get(word) == null) {
                map.put(word, 1);
            } else {
                int val = map.get(word);
                map.put(word, val + 1);
            }
        }

        // 建立小根堆
        PriorityQueue<Map.Entry<String, Integer>> queue = new PriorityQueue<>(
                new Comparator<Map.Entry<String, Integer>>() {
                    @Override
                    public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                        if (o1.getValue().compareTo(o2.getValue()) == 0) {
                            return o2.getKey().compareTo(o1.getKey());
                        }
                        return o1.getValue().compareTo(o2.getValue());
                    }
                });
        for (Map.Entry<String, Integer> entry : map.entrySet()) {
            if (queue.size() < k) {
                queue.offer(entry);
            } else {
                Map.Entry<String, Integer> tmp = queue.peek();
                if (tmp.getValue().compareTo(entry.getValue()) < 0) {
                    queue.poll();
                    queue.offer(entry);
                } else {
                    // 按照字符顺序排
                    if (tmp.getValue().compareTo(entry.getValue()) == 0) {
                        if (tmp.getKey().compareTo(entry.getKey()) > 0) {
                            queue.poll();
                            queue.offer(entry);
                        }
                    }

                }
            }
        }

        List<String> list = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            Map.Entry<String, Integer> tmp = queue.poll();
            list.add(tmp.getKey());
        }

        Collections.reverse(list);
        return list;
    }
    public static void main(String[] args) {
        String[] words = new String[]{"i","love","leetcode","i","love","coding"};
        System.out.println(topKFrequent(words, 1));
    }
}
